A typical network router receives and transmits packets in order to transfer these packets along paths within a network. Generally, such a router receives a packet from one portion of the network through a first network interface (i.e., a network port, link, interface device, etc.), and transmits that packet through another network interface to another portion of the network based on routing information associated with that packet, in order to forward or xe2x80x9croutexe2x80x9d that packet from its source towards its intended destination.
Some network routers receive and transmit packets using interrupts. FIG. 1 illustrates such a router 20. The router 20 includes interfaces 22 (e.g., 22-1, . . . , 22-G) and an interconnection mechanism 24. Each interface 22 includes a receive circuit RC which receives packets 25 from a network (not shown) and a transmit circuit TM which transmits packets 25 to the network. Each receive circuit RC includes a receive queue 32 and a receive interrupt status flag (or bit) 34. Each transmit circuit TM includes a transmit queue 36 and a transmit interrupt status flag (or bit) 38. Typically, the transmit queue 36 is smaller than the receive queue 32. For example, in a Weighted Fair Queuing implementation, the transmit queue 36 may be capable of holding only one or two packets while the receive queue 32 is capable of holding several packets. In other configurations, the transmit queue 36 may be configurable and not necessarily capable of only holding one or two packets.
It should be understood that the respective receive and transmit circuits RC, TM of each interface 22 typically reside together, e.g., as a single device or on a single printed circuit board (PCB). As such, the pair of receive and transmit interrupt status flags 34, 38, which belong to the receive and transmit circuits RC, TM of a particular interface 22, typically reside together in a single memory location or register (e.g., an interrupt status register) which is readable by a single read operation.
The interconnection mechanism 24 includes memory 26 and a processor or central processing unit (CPU) 28. The memory 26 stores an operating system 30 and software queues 40 which are respective extensions of the transmit queues 36 of the transmit circuits TM. For example, a first software queue 40 temporarily stores packets 25 to be transmitted by a transmit circuit 22-1-TM of a first interface 22-1, a second software queue 40 temporarily stores packets 25 to be transmitted by a transmit circuit 22-2-TM of a second interface 22-2, and so on.
When the router 20 is in a normal operating mode, the operating system 30 directs the processor 28 to perform a procedure 50 to fully attend to each interface 22 in a round robin manner. That is, the operating system 30 directs the processor 28 to select an interface 22 (e.g., interface 22-1), handle any transmit interrupts for the selected interface 22 by moving any packets 25 which are ready for transmission from that interface""s software queue 40 to that interface""s transmit queue 36, subsequently handle any receive interrupts for the selected interface 22 by processing packets 25 from that interface""s receive queue 32, and then proceed to handle the next interface 22 (e.g., interface 22-2) in a similar manner. When the processor 28 processes a packet 25 from a receive queue 32, the processor typically (i) identifies an interface 22 through which to transmit that packet 25 based on routing information associated with that packet 25 (e.g., a destination address residing in the header of that packet), and (ii) moves that packet 25 to the transmit queue 36 of the identified interface 22 if that transmit queue is not full, or to the software queue 40 associated with the identified interface 22 if that transmit queue 36 is full. It should be understood that the processor 28 may or may not be able to respond immediately to the receive and transmit interrupts depending on whether there exists any higher priority tasks or interrupt handlers.
FIG. 2 illustrates further details of this procedure 50. In step 52, the processor 28 selects an interface 22. To this end, the processor 28 reads the contents of a memory location of the selected interface 22 containing the receive and transmit interrupt status flags 34, 38 of that interface 22.
In step 54, if the transmit interrupt status flag 38 of the selected interface 22 indicates that a transmit interrupt is pending for the transmit circuit TM of the selected interface 22, the processor 28 proceeds to step 56. Otherwise, the processor 28 proceeds to step 58.
In step 56, the processor 28 handles the pending transmit interrupt of the selected interface 22. Typically, step 58 involves the processor 28 executing a transmit interrupt handler (part of the operating system 30) for the selected interface 22. The transmit interrupt handler directs the processor 28 (i) to reset the transmit interrupt status flag 38 of that interface 22, and (ii) to move any packets 25 residing in a software queue 40 associated with that interface 22 from that software queue 40 to the transmit queue 36 of the transmit circuit TM of that interface 22.
In step 58, if the receive interrupt status flag 34 of the selected interface 22 indicates that a receive interrupt is pending for the receive circuit RC of the selected interface 22, the processor 28 proceeds to step 60. Otherwise, the processor 28 proceeds to step 62.
In step 60, the processor 28 handles the receive interrupt of the selected interface 22. Typically, in step 60, the processor 28 executes a receive interrupt handler (part of the operating system 30) for that interface 22. The receive interrupt handler directs the processor 28 (i) to reset the receive interrupt status flag 38 of that interface 22, and (ii) to move any packets 25 residing in the receive queue 32 of the receive circuit RC of that interface 22 to their appropriate software queue 40.
In step 62, the processor 28 determines whether it should continue normal operation, i.e., continue to attend to the interfaces 22. If the processor 28 determines that it should terminate normal operation (e.g., if the processor 28 receives a shutdown or reset command), the processor 28 terminates the procedure 50. Otherwise, step 62 proceeds to step 64.
In step 64, the processor 28 selects another interface 22. Step 64 then proceeds back to step 54 for another pass of steps 54 through 62.
It should be understood that each pass of steps 54 through 62 forms a larger step 66 of handling any transmit and receive interrupts for the currently selected interface 22. Each time the processor 28 performs step 64, the processor 28 selects a different interface 22 until the processor 28 has selected each interface 22. Accordingly, the operation of the router 20 essentially involves the steps of selecting an interface 22, handling any transmit and receive interrupts for that interface 22, and then repeating these steps for the remaining interfaces 22 to continuously attend to the interfaces 22 such that the processor 28 selects and attends to the interfaces 22 in a round robin manner.
Historically, a common belief is that a conventional router""s processor or CPU is not a major source of performance difficulties. That is, it is commonly believed that the processor is not a bottleneck and that packets do not have a tendency to accumulate within the router. Under this belief, it is viewed that, as fast as the packets arrive at the router, the router selects interfaces and transmits the packets through the selected interfaces. This may be true if the router""s packet forwarding paths are simple to determine. For example, this may be true if the router operates according to a queuing algorithm which uses a simple first-in-first-out (FIFO) approach.
However, recent advances have provided opportunities for a router""s processor to become a source of performance drawbacks. In particular, factors such as the deployment of new Quality of Service (QoS) features and more complex policy-based networking approaches are making packet processing more complicated and burdensome on a router""s processor.
In general, the majority of packet processing involves the determination of the packet forwarding path. For example, packet classification and policy-based scheduling may require extensive searching through an access control list (ACL) which can be very time consuming and demanding on a router""s CPU. Additionally, flow-based weighted fair queuing (WFQ) approaches may require extensive searching of a queue list to determine the next packet to be transmitted. Furthermore, as network topologies grow and become more complex, the calculation and distribution of routing information may require more routing time and processing operations. Accordingly, the demands on the router""s processor may further increase in the future.
The invention is based in part on the observation that conventional routers (i) can be particularly susceptible to CPU bottlenecks caused by growing routing decision complexity, and (ii) may become more susceptible to such bottlenecks because conventional routers do not handle transmit interrupts in a very timely manner. This drawback stems in part from the earlier-described conventional round robin approach implemented by conventional routers. In this conventional approach, the router""s processor fully attends to any transmit and receive interrupts of one interface before proceeding to fully attend to those interrupts of the next interface, and so on. When the router""s processor attends to an interface, the router""s processor selects an interface, handles any transmit interrupts of that interface, subsequently handles any receive interrupts of that interface, and then proceeds to do the same for another interface until the processor has attended to each interface in round robin fashion. This approach is a potential cause of starvation by the transmit circuits of the interfaces of such a router. Further details of this drawback will now be explained by the following example.
Suppose that the router 20 of FIG. 1 uses a flow-based WFQ approach to route packets 25. Under this approach, the router 20 does not know which packet 25 to send until the router 20 transmits a currently processed packet 25. Under this approach, the transmit queues 36 of the transmit circuits TM of the router interfaces 22 are typical in size, i.e., capable of holding only one or two packets 25 at a time.
During operation, as the transmit circuit TM of each interface 22 completes transmission of a packet 25, that interface 22 sends a transmit interrupt to the processor 28 (e.g., identified by the transmit interrupt flag 38 of that interface 22). If the processor 28 is not busy (i.e., if there is no CPU bottleneck), the processor 28 will execute a transmit interrupt handler for that interface 22 in order to move any packets 25 available for transmission through that interface 22 into the transmit queue 36 of that interface 22. In this situation, the processor 28 is capable of keeping the transmit circuit TM of that interface 22 busy.
However, if the processor 28 is busy handling a receive interrupt (executing a receive interrupt handler for another interface 22), the transmit circuit TM will have to wait for the processor 28 to complete its work of handling the receive interrupt of the other interface 22. As the processor 28 handles the receive interrupt of the other interface 22, the processor 28 may process several packets 25 from the receive queue 32 of the receive circuit RC of that other interface 22.
Unfortunately, with the WFQ approach, the processing of each packet 25 is particularly time consuming. In particular, for each packet 25, the processor 28 typically performs a lookup operation using the ACL, or performs a computation, to select the interface 22 through which to transmit the next packet 25 (i.e., to determine the next hop and/or virtual time for forwarding the next packet 25). Since the processor 28 handles both the transmit and receive interrupts for one interface 22 after another, the initial interface 22 that sent the transmit interrupt may wait a substantial amount of time before the processor 28 is ready to handle that transmit interrupt. Accordingly, conventional routers 20, such as that described-above, are highly susceptible to CPU bottlenecks and associated performance degradation drawbacks.
In contrast to conventional routers which, for each network interface, fully attend to any transmit and receive interrupts of that interface before attending to another interface, the invention is directed to techniques for moving data elements (e.g., packets, frames, cells, etc.) within a data communications device which gives higher priority to handling transmit interrupts relative to handling receive interrupts. In one arrangement, the data communications device exclusively runs all of the transmit interrupt handlers to provide data elements to network interfaces for transmission prior to running receive interrupt handlers to process received data elements, and provides global weighted preferential treatment to these transmit interrupts in order to minimize the idle times of transmit circuits of the interfaces.
In one arrangement, a data communications device includes multiple network interfaces which are capable of transmitting and receiving data elements with a network. The data communications device further includes a controller, coupled to the multiple network interfaces. The controller is configured to perform a method comprising the steps of: (A) determining which of the multiple network interfaces indicates readiness to transmit a data element to the network and which of the multiple network interfaces indicates receipt of a data element from the network; (B) exclusively running, for each network interface indicating readiness to transmit a data element to the network, a transmit interrupt handler to load that network interface with a data element for transmission if such a data element is available for transmission within the data communications device; and (C) after step B, running, for at least one network interface which indicates receipt of a data element from the network, a receive interrupt handler to process that data element. Since the data communications device exclusively runs transmit interrupt handlers before any receive interrupt handlers, the data communications device is less likely to delay handling transmission of data elements through the network interfaces. In general, this arrangement allows the data communications device to handle transmit interrupts as early as possible to move data elements quickly to the network interfaces. Accordingly, this arrangement gives higher priority to handling transmit interrupts over handling receive interrupts, and it is less likely that network interfaces will xe2x80x9cstarvexe2x80x9d for data elements.
In one arrangement, a situation may arise when more than N network interfaces indicate receipt of a data element from the network, N being a positive integer. In this arrangement, the controller is configured such that step C involves (i) running, for N network interfaces indicating receipt of a data element from the network, a receive interrupt handler to process that data element; and (ii) refraining from running receive interrupt handlers for more than the N network interfaces until step A and step B are repeated. Accordingly, the controller has the opportunity to again attend to transmit interrupts thus reducing idle time of transmit circuits of the interfaces.
In another arrangement, a situation may arise where the network interfaces receive more than X data elements, X being a positive integer. In this arrangement, the controller is configured such that step C involves (i) running, for at least one network interface indicating receipt of a data element from the network, a receive interrupt handler to process that data element until X data elements have been processed; and (ii) refraining from processing more than the X data elements until step A and step B are repeated. As a result, the controller has the opportunity to again attend to transmit interrupts thus lowering idle time of transmit circuits of the interfaces.
In one arrangement, the controller is configured such that step C involves (i) running, for a particular network interface which indicates receipt of a first data element from the network, a transmit interrupt handler to load the particular network interface with a second data element for transmission if such a second data element is available for transmission within the data communications device; and (ii) subsequently running a receive interrupt handler to process the first data element. Accordingly, when the controller is ready to handle a receive interrupt for a particular network interface, the controller checks whether there is a transmit interrupt pending for that interface and handles that transmit interrupt before handling the receive interrupt. As a result, the controller can give priority to any transmit interrupt that occurs on that interface between the time the controller initially checks for interrupts, and the time the controller is ready to handle a receive interrupt for that interface.
In another arrangement, the controller is configured such that step C involves (i) running, for a particular network interface which indicates receipt of a data element from the network, a receive interrupt handler to process that data element; and (ii) running a transmit interrupt handler for another interface through which that data element is to be transmitted if a transmit interrupt is pending for that other interface. In this arrangement, the controller can check the interface through which that data element is to be transmitted and handle any transmit interrupt for that interface. Accordingly, the controller can give priority to any transmit interrupt pending at that interface over handling another receive interrupt.
In one arrangement, the controller is configured such that the method further includes the step of assigning weights to the network interfaces based on transmission capacities of the network interfaces such that, in step B, transmit interrupt handlers for the network interfaces run in an order determined by the assigned weights.
In another arrangement, the controller is configured such that the method further includes the step of assigning weights to the network interfaces based on numbers of data elements ready for transmission through each network interface such that, in step B, transmit interrupt handlers for the network interfaces run in an order determined by the assigned weights.
In another arrangement, the controller is configured such that the method further includes the step of assigning weights to the network interfaces based on transmission capacities of the network interfaces and numbers of data elements ready for transmission through each network interface such that, in step B, transmit interrupt handlers for the network interfaces run in an order determined by the assigned weights.
In yet another arrangement, the controller is configured such that the method further includes the step of assigning weights to the network interfaces based on respective numbers of processed data elements which are ready for transmission through the network interfaces such that, in step B, transmit interrupt handlers for the network interfaces run in an order determined by the assigned weights.
In any of the above-described arrangements, the assignment of weights to the interfaces and the running of transmit interrupt handlers for the interfaces in an order based on the assigned weights enables the techniques of the invention to provide weighted preferential treatment to the transmit interrupts in addition to the already described preferential treatment of transmit interrupts over receive interrupts.
In another arrangement, a data communications device includes a first network interface which stores a data element to be processed by data communications device, a second network interface, and an interconnection mechanism coupled to the first and second network interfaces. The interconnection mechanism includes (i) memory which stores a first processed data element and a second processed data element, and (ii) a controller. The controller is configured to perform a method comprising the steps of: (A) moving a first processed data element from the interconnection mechanism to the first network interface for transmission of the first processed data element into a network through the first network interface; (B) after step A, moving a second processed data element from the interconnection mechanism to the second network interface for transmission of the second processed data element into the network through the second network interface; and (C) after step B, moving the data element stored by the first network interface from the first network interface to the interconnection mechanism.
In addition to the above-described method and data communications device arrangements, other arrangements of the invention are directed to a computer program product. In one arrangement, the computer program product includes a computer readable medium having instructions stored thereon. The instructions, when processed by a data communications device having multiple network interfaces which are capable of transmitting and receiving data elements with a network, cause the data communications device to perform the steps of: (A) determining which of the multiple network interfaces indicates readiness to transmit a data element to the network and which of the multiple network interfaces indicates receipt of a data element from the network; (B) exclusively running, for each network interface indicating readiness to transmit a data element to the network, a transmit interrupt handler to load that network interface with a data element for transmission if such a data element is available for transmission within the data communications device; and (C) after step B, running, for at least one network interface which indicates receipt of a data element from the network, a receive interrupt handler to process that data element.
The features of the invention, as described above, may be employed in data communications devices and other computerized devices such as those manufactured by Cisco Systems, Inc. of San Jose, Calif.